這題要實作一個 LRU (Least Recently Used) cache，就是當超過容量時，會淘汰最久沒被用的元素，需要實作一個 LRUCache 類別，要有兩個主要功能：get(key)返回對應鍵的值，如果不存在就返回 -1、put(key, value)如果鍵存在，更新其值；如果鍵不存在，就把新的鍵值對插到 cache 中，如果插入導致 cache 超過容量，就要移除最少用的鍵，為了達到 O(1) 的時間複雜度，用兩個資料結構是比較保險，哈希表 (HashMap)用來快速檢索鍵對應的值，雙向鏈表，用來追蹤最近使用順序，最左是最久沒用的，最右是最新用的，雙向鏈表的設計允許在 O(1) 時間內把元素移到最前面，或從尾刪元素。

步驟：
設計雙向鏈表，每個節點包含 key、value、prev 和 next，用來記前後關係，這樣可以在 O(1) 時間內把任意節點移動或刪除，HashMap (字典)，用來存 key 到對應鏈表節點的映射，方便快速查詢。
操作get ，如果鍵存在字典中，就移動該節點到鏈表最前面，在返回其值，如果鍵不存在，返回 -1。
操作put ，如果鍵已經存在，更新該節點值再把它移到最前面，如果鍵不存在，創一個新節點再插到鏈表最前面，如果超過容量，就刪鏈表末尾節點。
程式碼：
class ListNode:
def init(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache(object):

def __init__(self, capacity):
    """
    :type capacity: int
    """
    self.capacity = capacity
    self.cache = {}  # 儲存 key -> node 映射
    self.head = ListNode()  # 虛擬頭節點
    self.tail = ListNode()  # 虛擬尾節點
    self.head.next = self.tail
    self.tail.prev = self.head

def get(self, key):
    """
    :type key: int
    :rtype: int
    """
    if key in self.cache:
        node = self.cache[key]
        self._move_to_front(node)
        return node.value
    return -1

def put(self, key, value):
    """
    :type key: int
    :type value: int
    :rtype: None
    """
    if key in self.cache:
        node = self.cache[key]
        node.value = value
        self._move_to_front(node)
    else:
        if len(self.cache) >= self.capacity:
            self._remove_last()
        new_node = ListNode(key, value)
        self._add_to_front(new_node)
        self.cache[key] = new_node

def _move_to_front(self, node):
    # 把節點移到鏈表的最前面
    self._remove(node)
    self._add_to_front(node)

def _remove(self, node):
    # 從鏈表中移除節點
    prev_node = node.prev
    next_node = node.next
    prev_node.next = next_node
    next_node.prev = prev_node

def _add_to_front(self, node):
    # 把節點加到鏈表最前面
    next_node = self.head.next
    self.head.next = node
    node.prev = self.head
    node.next = next_node
    next_node.prev = node

def _remove_last(self):
    # 移除鏈表最後一個節點
    last_node = self.tail.prev
    self._remove(last_node)
    del self.cache[last_node.key]

解釋：
初始化，創一個容量為 capacity 的快取，設雙向鏈表的虛擬頭和尾來方便管理節點，get 操作，如果鍵存在於快取中，把它對應節點移到最前面並返回值，如果不存在，返回 -1，put 操作，如果鍵已存在，更新值並把節點移到最前面，如果鍵不存在，插入新節點，如果容量超過上限，移掉最久沒用的節點。
輔助：_move_to_front 負責把節點移到鏈表最前面，_remove 和 _add_to_front 負責在雙向鏈表中插入或移除節點，_remove_last 用來刪最久沒用的節點。
心得：
這題是資料結構設計問題，解決方案涉及對雙向鏈表和哈希表的應用，對每個操作，要求 O(1) 的時間複雜度，所以我選擇這兩個結構配合用，這題幫我鞏固雙向鏈表的實作跟它和哈希表的結合，尤其是怎麼設計高效的資料結構來滿足實際應用，學到關鍵技巧是怎樣通過雙向鏈表來追蹤元素的使用順序，並實現 LRU 這樣一個具實際應用意義的策略。